1. Field of the Invention
The invention relates to the field of communication. More specifically, the invention relates to communication networks.
2. Background of the Invention
A router hosts a routing protocol(s) that can include the Routing Information Protocol (RIP), Open Short Path First (OSPF), Intermediate System to Intermediate System (IS—IS), the Border Gateway Protocol (BGP), etc. The router exchanges messages with neighboring routers in accordance with one or more of the hosted routing protocols.
FIG. 1 (PRIOR ART) is a diagram illustrating a BGP update message. The BGP update message 100 includes an attributes section 101 and a network layer reachability information (NLRI) section 103. The attributes section 101 identifies various attributes defined by “A Border Gateway Protocol 4”, Request for Comments 1771 by Y. Rekhter and T. Li (March 1995) (RFC 1771) that describe a path. These attributes include origin, next hop, autonomous system (AS) path, local preference, etc. The NLRI section 103 identifies destinations that can be reached via the path described by the attributes in the attributes section 101.
When a router that hosts BGP receives a BGP update message from one of its neighbors, the router updates its BGP routing table in accordance with the update message received. The BGP routing table of a router can include a large number of paths.
FIG. 2 (PRIOR ART) is a diagram illustrating a BGP table. The BGP table 200 includes a destination data structure 202 and an attribute table 201. Each element of the destination data structure 201 identifies a network prefix (e.g., an IP prefix). The element 203A is the root of the destination data structure 202. The element 203C references a linked list of path data structures 205A and 205B. One of the path data structures 205A and 205B corresponds to a best path to the destination identified by the element 203C. The path data structure 205A references the first entry in the attribute table 201. The path data structure 205B references the second entry in the attribute table 201. If the path data structure 205B corresponds with the best path to the network prefix identified by the element 203C, then the attributes in the second entry of the attribute table described that best path. An element 203D references a path data structure 205C. The path data structure 205C also references the second entry in the attribute table 201. An element 203B references a path data structure 205C, which references the last entry in the attribute table 201.
When a BGP update message is built in accordance with Appendix 6.1 of the RFC 1771, a BGP process packs network prefixes into the update message as illustrated in FIG. 1. The RFC 1771 describes address prefix oriented routing update. In other words, the BGP process builds update messages as it processes each network prefix. As each network prefix in the destination data structure 202 is processed, the BGP process allocates a BGP update message for the corresponding attributes. Each time the BGP process encounters a network prefix that corresponds to attributes of an allocated message, the BGP process appends the network prefix to the message. Each time the BGP process encounters a network prefix that corresponds to attributes that do not have an allocated message, the BGP process allocates a new update message. After the entire BGP table has been scanned, the BGP process transmits the messages and releases resources utilized for the messages.
Assuming changes are detected in the destination data structure 202, a router that hosts the BGP table 200 will begin to build BGP update messages with network prefixes identified by marked elements. Assuming that the elements 203B–203D have been marked as changed, a BGP process allocates an update message for the last entry in the attribute table 201 when the BGP process encounters the element 203B of the destination data structure 202. The network prefix identified by the element 203B is appended to the allocated message. The BGP process continues through the destination data structure 202 and allocates another update message for the first entry in the attribute table 201 when the BGP process encounters the element 203C. The BGP process allocates a third message for the second entry in the attribute table 201 when it encounters the path data structure 205B, which references the second entry. The BGP process appends the network prefix identified in the element 203C in the second and third allocated messages. The BGP process appends the network prefix identified in the element 203D to the third allocated message. Once the BGP process completes walking the destination data structure, the BGP process transmits all messages allocated for the routing table 200 and releases resources (e.g. memory) utilized for the messages.
Several years ago, this method of building BGP update messages was acceptable since a routing table identified a relatively small number of paths (e.g., a few thousand paths). This method is inefficient when applied to a routing table that identifies a very large number of paths (e.g., hundreds of thousands of paths). Allocating resources for a large number of update messages consumes vast amounts of a router's resources, and can possibly deplete its resources.
An alternative approach transmits allocated messages upon reaching a predetermined limit, such as a limit of resources. This alternative approach reduces packing efficiency of update messages. Since allocated messages are transmitted before all network prefixes are processed, the same set of attributes may be identified in multiple update messages. The transmitting network device's resources are still not utilized efficiently. Processor time spent on allocating and transmitting these update messages will increase in relation to the reduction in packing efficiency. Furthermore, resources of network device's that receive these update messages are also utilized inefficiently because of reduced packing efficiency.